package leetcode.editor.week.week309;

// 6168. 恰好移动 k 步到达某一位置的方法数目
// https://leetcode.cn/problems/number-of-ways-to-reach-a-position-after-exactly-k-steps/
public class Solution6168 {
    int MOD = (int) 1E9 + 7;

    // https://leetcode.cn/problems/number-of-ways-to-reach-a-position-after-exactly-k-steps/solution/j-by-na-ge-shui-o-hdj8/
    public int numberOfWays(int startPos, int endPos, int k) {
        // 根据数据范围来开辟空间
        // dp[i][j]表示到达位置i，花费j步的方案
        int[][] dp = new int[3010][1010];
        startPos += 1000;
        endPos += 1000;
        // 初始化
        dp[startPos - 1][1] = 1;
        dp[startPos + 1][1] = 1;
        for (int i = 2; i <= k; i++) {
            for (int j = startPos - k; j <= startPos + k; j++) {
                // 上一个找左右步数减一
                dp[j][i] = (dp[j - 1][i - 1] + dp[j + 1][i - 1]) % MOD;
            }
        }

        return dp[endPos][k];
    }

    // TODO DFS

}
